class Solution {
    List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        if (root == null) return new ArrayList<>(); // 特殊情况
        ArrayList<Integer> list = new ArrayList<>();
        list.add(root.val);
        helper(root, target, list, root.val);
        return result;
    }

    // list 用于存放结果路径   sum 用于存放目前的路径和
    public void helper(TreeNode root, int target, ArrayList<Integer> list, int sum) {
        if (sum == target && root.left == null && root.right == null) { // 递归退出条件
            result.add(new ArrayList<>(list));
        } else {
            // 向左走
            if (root.left != null) {
                list.add(root.left.val);
                helper(root.left, target, list, sum + root.left.val);
                list.remove(list.size() - 1);
            }

            // 向右走
            if (root.right != null) {
                list.add(root.right.val);
                helper(root.right, target, list, sum + root.right.val);
                list.remove(list.size() - 1);
            }
        }
    }
}